#pragma once
#include <assert.h>

namespace lst
{
    template<class T>
    struct list_node
    {
        T _data;// 存储节点的数据
        list_node<T> *_next;
        list_node<T> *_prev;

        list_node(const T& val = T())
            :_data(val),
            _next(nullptr),
            _prev(nullptr)
        {}
    };
    // 迭代器实现
    /*Ref：引用类型;Ptr：指针类型
    在模版中引入这两个参数，__list_iterator就可以同时支持非const迭代器和
    const迭代器这两种迭代器形式，而不需要为每种形式写独立的代码*/
    template<class T,class Ref,class Ptr>
    struct __list_iterator
    {
        typedef list_node<T> Node;
        typedef __list_iterator<T,Ref,Ptr> self;
        Node* _node;

        __list_iterator(Node* node)
            :_node(node)
        {}

        self& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        self operator++(int)
        {
            self tmp(*this);
            _node = _node->_next;
            return tmp;
        }
        self operator--(int)
        {
            self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }
        Ref operator*() const
        {
            return _node->_data;
        }
        // 供自定义类型使用
        Ptr operator->() const
        {
            return &_node->_data;
        }
        bool operator!=(const self& s)
        {
            return _node != s._node;
        }
        bool operator==(const self& s)
        {
            return _node == s._node;
        }
    };
    //反向迭代器
    template<class Iterator,class Ref,class Ptr>
    class ReverseListIterator
    {
    public:
        typedef ReverseListIterator<Iterator,Ref,Ptr> self;
        Iterator _it;
        // 构造
        ReverseListIterator(Iterator it)
            :_it(it)
        {}
        self& operator++()
        {
            --_it;
            return *this;
        }
        self& operator--()
        {
            ++_it;
            return *this;
        }
        self operator++(int)
        {
            self temp(*this);
            --_it;
            return temp;
        }
        self operator--(int)
        {
            self temp(*this);
            ++_it;
            return temp;
        }
        Ref operator*()
        {
            return *_it;
        }
        Ptr operator->()
        {
            return _it.operator->();
        }
        bool operator!=(const self& l)const
        {
            return _it != l._it;
        }
        bool operator==(const self& l)const
        {
            return _it == l._it;
        }
    };

    template<class T>
    class list
    {
        typedef list_node<T> Node;
    public:
        typedef __list_iterator<T,T&,T*> iterator;
        typedef __list_iterator<T,const T&,const T*> const_iterator;

        typedef ReverseListIterator<iterator,T&,T*> reverse_iterator;
        typedef ReverseListIterator<const_iterator,T&,T*> const_reverse_iterator;

        iterator begin()
        {
            // 返回_head->_next，而返回参数是iterator，那么会隐式调用__list_iterator的构造函数
            return _head->_next;
        }
        iterator end()
        {
            return _head;
        }
        const_iterator begin() const
        {
            return _head->_next;
        }
        const_iterator end() const
        {
            return _head;
        }

        reverse_iterator rbegin()
        {
            return reverse_iterator(--end());
        }
        reverse_iterator rend()
        {
            return reverse_iterator(end());
        }
        const_reverse_iterator rbegin() const
        {
            return const_reverse_iterator(--end());
        }
        const_reverse_iterator rend() const
        {
            return const_reverse_iterator(end());
        }
        //空链表初始化
        void empty_init()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
            _size = 0;
        }
        list()
        {
            empty_init();
        }
        list(const list<T>& lt)
        {
            empty_init();
            for (auto e: lt)
            {
                push_back(e);
            }
        }
        void swap(list<T>& lt)
        {
            std::swap(_head,lt._head);
            std::swap(_size,lt._size);
        }
        list<T>& operator=(const list<T> lt)
        {
            swap(lt);
            return *this;
        }
        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

        size_t size() const
        {
            return _size;
        }

        void push_back(const T& val)
        {
            Node* tail = _head->_prev;
            Node* newnode = new Node(val);
            tail->_next = newnode;
            newnode->_prev = tail;
            newnode->_next = _head;
            _head->_prev = newnode;
            ++_size;
            // insert(end(),val);
        }
        void push_front(const T& val)
        {
            insert(begin(),val);
        }
        void pop_back()
        {
            erase(--end());
        }
        void pop_front()
        {
            erase(begin());
        }
        iterator insert(iterator pos, const T& val)
        {
            Node* cur = pos._node;
            Node* newnode = new Node(val);
            newnode->_data = val;
            newnode->_prev = cur->_prev;
            newnode->_next = cur;

            cur->_prev = newnode;
            newnode->_prev->_next = newnode;

            ++_size;

            return iterator(newnode);
        }
        iterator erase(iterator pos)
        {
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;
            delete cur;
            prev->_next = next;
            next->_prev = prev;

            --_size;
            return iterator(next);
        }
        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }
    private:
        Node *_head;// 哨兵位头结点
        size_t _size;// 记录元素的个数
    };

    // 打印容器函数
    template<typename Container>
    void print_container(const Container& con)
    {
        /*注意：当你模板类的嵌套类型（如list<T>::iterator）时，
         *编译器需要明确地知道iterator是一个类型，而不是一个对象或成员变量。
         *所以必须使用typename关键字来显式地告诉编译器，这是一个类型。*/
        typename Container::const_iterator it = con.begin();
        //这里的typename告诉编译器，Container::iterator是一个类型，而不是其他东西
        while (it != con.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }
    void test()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        list<int>::reverse_iterator it = lt.rbegin();
        cout << *it;
    }
}
